// https://www.lintcode.com/problem/combination-sum-ii

public class Solution {
    /**
     * @param num: Given the candidate numbers
     * @param target: Given the target number
     * @return: All the combinations that sum to target
     */
    public List<List<Integer>> combinationSum2(int[] num, int target) {
        // write your code here
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(num);
        _combinationSum2(ret, target, num, new ArrayList<>(), 0, 0);
        return ret;
    }

    protected void _combinationSum2(List<List<Integer>> ret, int target, int[] num, List<Integer> comb, int i, int sum) {
      if (sum == target) {
        ret.add(new ArrayList<>(Arrays.asList(new Integer[comb.size()])));
        Collections.copy(ret.get(ret.size() - 1), comb);
      } else if (sum < target) {
        if (i <= num.length) {
          int prev = (num.length > 0) ? num[0] - 1 : -1;
          int j = i;
          while (j < num.length) {
            if (num[j] != prev) {
              prev = num[j];
              comb.add(num[j]);
              _combinationSum2(ret, target, num, comb, j + 1, sum + prev);
              comb.remove(comb.size() - 1);
            }
            ++j;
          }
        }
      }
    }
}